public class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(k == 0) {
            return ret;
        }
        ret = createHeap(arr,k);
        for(int i = k;i < arr.length;i++) {
            if(arr[i] < ret[0]) {
                ret[0] = arr[i];
                siftDown(ret,0,k);
            }
        }
        return ret;
    }

    public int[] createHeap(int[] arr,int k) {
        int[] ret = new int[k];
        int usedSize = 0;
        for(int i = 0;i < k;i++) {
            ret[i] = arr[i];
            usedSize++;
        }
        for(int i = (k - 2)/2;i >= 0;i--) {
            siftDown(ret,i,usedSize);
        }
        return ret;
    }

    public void siftDown(int[] ret,int parent,int k) {
        int child = 2 * parent + 1;
        for(int i = parent;i >= 0;--i) {
            while(child < k) {
                if(child + 1 < k && ret[child] < ret[child + 1]) {
                    child++;
                }
                if(ret[child] > ret[parent]) {
                    Swap(ret,child,parent);
                }
                parent = child;
                child = 2 * parent + 1;
            }
        }
    }

    public void Swap(int[] arr,int x,int y) {
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
}
